package algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class 俄罗斯套娃信封问题 {
    /*
     * 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w,
     * h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
     * 
     * 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
     * 
     * 说明: 不允许旋转信封。
     * 
     * 示例:
     * 
     * 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为:
     * [2,3] => [5,4] => [6,7]。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/russian-doll-envelopes
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int maxEnvelopes(int[][] envelopes) {
        // 3重循环超时了，将信封按照宽度进行排序，那么这个问题就可以根据高度，查询最大递增子序列长度了
        /*
         * 执行用时 : 663 ms , 在所有 Java 提交中击败了 19.56% 的用户 内存消耗 : 62.9 MB , 在所有 Java
         * 提交中击败了 13.07% 的用户
         */
        List<Num> nums = new ArrayList<>();
        for (int[] enve : envelopes) {
            nums.add(new Num(enve[0], enve[1]));
        }
        Comparator c = new Comparator<Num>() {

            @Override
            public int compare(Num o1, Num o2) {
                if (o1.w == o2.w) {
                    return o1.h - o2.h;
                } else {
                    return o1.w - o2.w;
                }
            }
        };
        Collections.sort(nums, c);

        int len = envelopes.length;
        int[] dp = new int[len + 5];
        for (int i = 0; i < len; i++) {
            Num out = nums.get(i);
            int max = dp[i];
            for (int j = 0; j < i; j++) {
                if (j != i) {
                    Num in = nums.get(j);
                    if (out.h > in.h && out.w > in.w) {
                        max = Math.max(max, dp[j] + 1);
                    }
                }
            }
            dp[i] = max;
        }
        int max = -1;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dp[i]);
        }
        return max + 1;
    }

    public static class Num {
        int w;
        int h;

        public Num(int w, int h) {
            this.w = w;
            this.h = h;
        }
    }

    public static void main(String[] args) {
        俄罗斯套娃信封问题 run = new 俄罗斯套娃信封问题();
        int[][] envelopes = { { 4, 5 }, { 4, 6 }, { 6, 7 }, { 2, 3 }, { 1, 1 } };
        System.out.println(run.maxEnvelopes(envelopes));
    }
}
